Shape is the lowest common denominator in describing objects, and hence plays an important part in the processing of visual information. Many powerful techniques depend upon the accurate representation of shape. For example, advances in three dimensional hardware acquisition devices, such as digitizers, magnetic resonance imaging systems, computed tomography devices, and laser scanners permit reconstruction of high quality three dimensional models of objects that have to be analyzed or visualized in a concise way. Such models can be described by their color, texture, and shape information, but color and texture (photometric data) are not always available depending on the reconstruction method or acquisition technique. Shape, on the other hand, needs to be accurately modeled, and the efficiency, accuracy, speed, etc., of the modeling of shape directly affect the utility of any system that makes use of a particular model for shape.
An important approach for representing the structure of a shape is to reduce it to a graph. Several methods have been proposed to reduce a shape into a graph, which can be classified into two main categories Reeb graph-based methods and Skeletal graph-based methods. The idea of Reeb graph is to construct a continuous function, usually a height function from one boundary source point to describe the topological structure and reveal the topological changes such as splitting and merging. Unfortunately, this type of graph does not capture the geometry of the shape.
Skeletal graph methods can capture the geometry of a shape. Skeletal graph-based methods compute a one-dimensional skeleton of an object and then convert it into a skeletal graph as its shape representation. A skeleton is a compact representation of a shape that maintains its topology. The concept of skeleton or medial axis was first introduced by Blum as the locus of centers of maximal disks in 2D or spheres in 3D that at least touch the boundary at two points. See, H. Blum, “A Transformation for Extracting New Descriptors of Shape,” in Proc. Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, Ed., Cambridge, Mass.: MIT Press, pp. 362-380 (November 1967). Each point of the skeleton is associated with a radius function that is the radius of its maximal disk/sphere. Therefore, the shape can be represented with less information than the original one. In addition, the shape can be fully recovered from its skeleton. Skeletal graph techniques, including the methods and software of the present invention, capture the topology of the shape and also its geometry.
A skeleton is a compact representation of a shape that maintains its topology. In general, the dimension of a skeleton is less than the dimension of the original object by at least one. For example, the skeleton of a 2D shape is a set of medial curves or centerlines. On the other hand, the skeleton of a 3D object is a set of medial surfaces. As a special case, for a 3D tubular object whose cross section is circular, the skeleton is a set of medial curves rather than medial surfaces. Reducing the dimensionality of the skeleton describing general shapes from medial surfaces to a set of medial curves is of importance in a wide range of applications. Example applications include virtual endoscopy, character animation and morphing, blood vessel analysis such as stenosis and aneurisms, object matching and retrieval, and collision detection. Medial curves are generally called curve skeletons (CS). A curve skeleton can be defined as a one-dimensional connected and smooth curve about which the object is locally symmetric.
Curve skeleton methods include topological thinning methods, distance transform methods, and potential field methods. The basic idea behind thinning methods is to iteratively peel off the object's boundary by identifying simple points, whose removal does not alter its topology. Curve skeletons are usually extracted by either checking the voxel's local neighborhood against a set of templates that prevents the deletion of topological nodes such as branch and end points or by pruning medial surfaces while preventing the removal of junctions between surfaces. Removal of simple points can be done either sequentially, in parallel, by following a specific direction, or by utilizing distance maps in governing the order of thinning. In general, thinning methods produce connected curve skeletons that preserve the object topology. However, preserving end points leads to many undesired small branches, which require post-processing.
The distance transform D(x) computes at each voxel x its minimum distance from the object's boundary. D(x) can be discretely approximated using chamfer metric (3,4,5), or continuously approximated using either the fast marching methods or the fast sweeping methods. The ridge voxels (singularities) of D(x) are locally centered with respect to the object's boundary. Any distance transform-based method involves three main steps: generation of the distance field, detection of ridge voxels, and reconnection of voxels into curve skeletons. Zhou and Toga proposed a voxel coding technique, in which each voxel is assigned two codes; the distance to a manually selected seed point and the distance to the object's boundary. See, Y. Zhou and A. W. Toga, “Efficient skeletonization of volumetric objects,” IEEE Transactions on Visualization and Computer Graphics, vol. 5, no. 3, pp. 196-209, 1999. Initially, curve skeletons are extracted as trajectories and then centered using some medialness function. The algorithm guarantees connected paths but not centeredness especially near branching nodes. Telea and Vilanova resampled the volumetric object along the major three axis; x, y, and z, resulting in three separate stacks of cross sections for the same object. See, A. Telea and A. Vilanova, “A robust level-set algorithm for centerline extraction,” in VISSYM '03: Proceedings of the symposium on Data visualisation 2003, 2003, pp. 185-194. Then, a level set-based centerline extraction method is used to compute the medial point of each 2D cross section in each volume independently. Finally, the common points of the resultant sets of medial points form the final skeleton. The convergence of their method is not guaranteed because the actual topology of a 3D object cannot be interpreted from its 2D cross-sections. Deschamps et al., select the end points of a branch of interest manually and then a fast marching front propagates from the starting point with a speed that is a function of the distance transform until it reaches the end point. See, T. Deschamps and L. Cohen, “Fast extraction of minimal paths in 3d images and applications to virtual endoscopy,” Medical Image Analysis, vol. 5, no. 4, 2001. Centerline paths are extracted using the gradient descent method. This worked well for tubular structures. However, for general shapes, whose cross sections are not perfectly tubular, the method generates the shortest paths rather than centered ones. Dey and Sun defined some medial geodesic function on the medial surface of the object, from which curve skeletons are extracted by erosion. See, T. K. Dey and J. Sun, “Defining and computing curve-skeletons with medial geodesic function,” in Proc. Sympos. Geometry Processing, 2006, pp. 143-152. Although the method is promising for thin structures, the computed curve skeletons always oscillate around the desired ones.
In potential field methods, the Euclidean distance field is replaced with another continuous function that has some medial properties. Then, curve skeletons are identified as the field extremum points. Chaung et al., computed the Newtonian potential field as their potential function. See, J.-H. Chuang, C.-H. Tsai, and M.-C. Ko, “Skeletonization of three-dimensional object using generalized potential field,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 11, pp. 1241-1251, 2000. Since their method is limited only to polygonal data, each vertex in the object is assumed to start a new curved skeleton, which is not practical assumption for noisy objects. Although generalizing the method to handle non polygonal data is possible, the computation of the potential function is very expensive because the potential value at every internal voxel of the object is a function of its entire boundary voxels. Cornea at al. extended the method to handle non-polygonal data. See, N. Cornea, D. Silver, X. Yuan, and R. Balasubramanian, “Computing hierarchical curve-skeletons of 3d objects.” The Visual Computer, 2005. They computed the critical points and low divergence points of the field force to identify the starting point of each curved skeleton. Again, the computation of the potential field is still very expensive even on fast workstation. Also, due to visibility errors while computing the potential function or mis-computation of the critical field points, the final skeleton is not guaranteed to be either centered or connected.
In general, existing 3D extraction techniques of curve skeletons from volumetric objects suffer from at least one of the following limitations: (1) curve skeletons are extracted from medial surfaces by different pruning methods. Therefore, the accuracy of the former is a function of the extraction of the later; (2) they require manual interaction to select the starting point of each curve skeleton, (3) they are computationally expensive, (4) they require heuristics to handle branching nodes, (5) they are dedicated to a specific category of 3D objects, and hence lack of generality, and finally (6) they are sensitive to boundary noise.
Curve skeletons represent an object from image data. Once an object is represented by a curve skeleton, the object's representation can be used for many important functions. In medical imaging, computed curve skeletons can serve as flight paths in virtual endoscopy applications (e.g., colonoscopy, bronchoscopy, angioscopy, etc. In robotics, curve skeletons can serve as optimal planned paths (i.e., the shortest or the safest) for robotic navigation. In computer graphics, curve skeletons serve in the generation of the control skeleton and the skinning process (i.e., assigns each surface triangle to a part of the skeleton) for character animation. In computer vision, curve skeletons serve as a graph for 3D shape matching and retrieval.
Accurate, flexible curve skeletons make any application in which they are used more powerful. Some problems associated with techniques for computing curve skeletons include noise, speed, computational complexity, lack of generality, and lack of automation.
Farag et al., “Robust Centerline Extraction Framework Using Level Sets”, Computer Vision & Pattern Recognition (CVPR), Jun. 20-26, 2005, provide a framework for computing centerlines of arbitrary 2D shapes and 3D tubular volumetric objects (e.g., stack of images), whose cross sections are nearly or perfectly circular. In this technique, an object centerline point is selected automatically as the point of global maximum Euclidean distance from the boundary, and is considered a point source Ps that transmits a wave front that evolves over time and traverses the object domain. The front propagates at each object point with a speed that is proportional to its Euclidean distance from the boundary. The motion of the front is governed by a nonlinear partial differential equation whose solution is computed efficiently using level set methods. Initially, the Ps transmits a moderate speed wave to explore the object domain and extract its topological information. Then, it transmits a new front that is much faster at centerline points than non central ones. As a consequence, centerlines intersect the propagating fronts at those points of maximum positive curvature. Centerlines are computed by tracking them, starting from each topological point until the Ps is reached, by solving an ordinary differential equation using an efficient numerical scheme. The technique is computationally inexpensive, and handles efficiently objects with complex topology such as loops. It is suitable for both 2D and 3D tubular objects. The computed centerlines are centered, connected, thin, and less sensitive to boundary noise. Extracted paths form a tree graph at no additional cost. However, there is no theoretical justification behind its speed model to guarantee convergence. Also, speed parameters are set heuristically and therefore prevent the framework from automation. Finally, the technique is limited to 3D objects having circular cross-sections.
A particular robotic vision navigation technique, is provided in Farag et al, “PDE Based Robust Robotic Navigation,” Canadian Conference on Computer and Robot Vision (CRV), May 9-11, 2005. The robotic vision implementation in the present application is applicable for 2D robotic path planning. Its framework is general in the sense that it can be used for both 2D and 3D environments. It generates a collision-free optimum path for partial or complete configuration space. Optimum planned paths can be controlled according to the surrounding environment and running conditions in order to follow the safest, shortest, or the hybrid path. However, there is no theoretical justification behind its speed model to guarantee convergence. Also, the speed parameters are set heuristically and hence prevent the framework from automation.